package _go

/*面试题 02.05. 链表求和
难度
中等

66

收藏

分享
切换为英文
接收动态
反馈
给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。



示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}

	tmp := &ListNode{0, nil}
	res := tmp
	//标示位
	f := 0
	for l1 != nil || l2 != nil || f == 1 {
		val := 0
		if l1 != nil && l2 != nil {
			val = l1.Val + l2.Val
		} else if l1 != nil {
			val = l1.Val
		} else if l2 != nil {
			val = l2.Val
		}
		//加进位
		if f == 1 {
			val += f
			f = 0
		}
		//计算算法有进位
		if val >= 10 {
			f = val / 10
			val = val % 10
		}
		//fmt.Printf("f %d val :%d\n",f,val)
		res.Next = &ListNode{val, nil}
		res = res.Next

		if l1 != nil {
			l1 = l1.Next
		}
		if l2 != nil {
			l2 = l2.Next
		}
	}

	return tmp.Next
}
